package leetcode.ge100;

class Solution_230 {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public static void main(String[] args) {
	}

	public int kthSmallest(TreeNode root, int k) {
		int left = countNode(root.left);
		if (left + 1 == k)
			return root.val;
		else if (left + 1 < k)
			return kthSmallest(root.right, k - left - 1);
		else
			return kthSmallest(root.left, k);
	}

	static int countNode(TreeNode root) {
		if (root == null)
			return 0;
		return 1 + countNode(root.left) + countNode(root.right);
	}

}
